using System;
using System.Collections.Generic;
using System.Linq;

// 邻接表图测试类
public class AdjacencyListTest
{
    public static void RunTest()
    {
        Console.WriteLine("========== 邻接表图测试 ==========");
        //测试(V = {0, 1, 2})
        DirectedWeightedGraph testGraph = new(3);
        //0->1 01
        testGraph.AddEdge(0, 1, 1);
        //0->2 02
        testGraph.AddEdge(0, 2, 2);
        //1->2 12
        testGraph.AddEdge(1, 2, 12);
        //2->0 20
        testGraph.AddEdge(2, 0, 20);

        Console.WriteLine("\n按 Enter 键继续测试...");
        Console.ReadLine();

        //删除0->2
        testGraph.RemoveEdge(0, 2);
        Console.WriteLine("0->2是否存在:" + testGraph.HasEdge(0, 2));

        Console.WriteLine("\n按 Enter 键继续测试...");
        Console.ReadLine();

        Console.WriteLine("0->1的权重应该是 01 ->:" + testGraph.GetWeight(0, 1));

        Console.WriteLine("\n按 Enter 键继续测试...");
        Console.ReadLine();

        testGraph.AddEdge(1, 0, 10);
        List<Edge> edges = testGraph.GetNeighbors(1);
        foreach (var edge in edges)
        {
            Console.WriteLine("1的邻居有" + edge.to + " 的权重应该是" + edge.weight);
        }

        Console.WriteLine("\n按 Enter 键继续测试...");
        Console.ReadLine();

        Console.WriteLine("所有边:" + testGraph.GetAllEdges().Count);
    }
}
    //边类
    public class Edge{
        public int to;//指向节点的标号
        public int weight;
        public Edge( int to, int weight){
            this.to = to;
            this.weight = weight;
        }
    }

    //节点类
    public class Vertex{
        public int id;
        public Vertex[] neighbors;
    }

//有向加权图（邻接表实现）
public class DirectedWeightedGraph{
   
    private List<Edge>[] graph;
    public DirectedWeightedGraph(int n){
        graph = new List<Edge>[n];
        for(int i = 0; i < n; i++){
            //每一个节点都对应一个列表，列表中存储的是相邻节点
            graph[i] = new List<Edge>();
        }
    }

    /// <summary>
    /// 添加一条边
    /// </summary>
    /// <param name="from">起点</param>
    /// <param name="to">终点</param>
    /// <param name="weight">权重</param>
    public void AddEdge(int from, int to, int weight){
        graph[from].Add(new Edge(to, weight));
    }

    public void RemoveEdge(int from, int to){
        //找到from对应的列表，然后删除对应的to
        graph[from].RemoveAll(edge => edge.to == to);
    }
    
    public bool HasEdge(int from, int to){
        foreach(var edge in graph[from]){
            if(edge.to == to){
                return true;
            }
        }
        return false;
    }

    public int GetWeight(int from, int to){
        foreach(var edge in graph[from]){
            if(edge.to == to){
                return edge.weight;
            }
        }
        return -1;
    }

    /// <summary>
    /// 获取from的相邻节点
    /// </summary>
    /// <param name="from"></param>
    /// <returns></returns>
    public List<Edge> GetNeighbors(int from){
        return graph[from];
    }

    /// <summary>
    /// 获取所有边
    /// </summary>
    /// <returns></returns>
    public List<Edge> GetAllEdges(){
        return graph.SelectMany(edges => edges).ToList();
    }

    public int GetVertexCount(){
        return graph.Length;
    }
}
